{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Subarray Min-Product"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #prefix-sum #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #前缀和 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxSumMinProduct"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #子数组最小乘积的最大值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一个数组的 <strong>最小乘积</strong> 定义为这个数组中 <strong>最小值</strong> <strong>乘以 </strong>数组的 <strong>和</strong> 。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，数组 <code>[3,2,5]</code> （最小值是 <code>2</code>）的最小乘积为 <code>2 * (3+2+5) = 2 * 10 = 20</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个正整数数组 <code>nums</code> ，请你返回 <code>nums</code> 任意 <strong>非空子数组</strong> 的<strong>最小乘积</strong> 的 <strong>最大值</strong> 。由于答案可能很大，请你返回答案对  <code>10<sup>9</sup> + 7</code> <strong>取余 </strong>的结果。</p>\n",
    "\n",
    "<p>请注意，最小乘积的最大值考虑的是取余操作 <strong>之前</strong> 的结果。题目保证最小乘积的最大值在 <strong>不取余</strong> 的情况下可以用 <strong>64 位有符号整数</strong> 保存。</p>\n",
    "\n",
    "<p><strong>子数组</strong> 定义为一个数组的 <strong>连续</strong> 部分。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,<strong>2,3,2</strong>]\n",
    "<b>输出：</b>14\n",
    "<b>解释：</b>最小乘积的最大值由子数组 [2,3,2] （最小值是 2）得到。\n",
    "2 * (2+3+2) = 2 * 7 = 14 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [2,<strong>3,3</strong>,1,2]\n",
    "<b>输出：</b>18\n",
    "<b>解释：</b>最小乘积的最大值由子数组 [3,3] （最小值是 3）得到。\n",
    "3 * (3+3) = 3 * 6 = 18 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [3,1,<strong>5,6,4</strong>,2]\n",
    "<b>输出：</b>60\n",
    "<b>解释：</b>最小乘积的最大值由子数组 [5,6,4] （最小值是 4）得到。\n",
    "4 * (5+6+4) = 4 * 15 = 60 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= nums.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 <= nums[i] <= 10<sup>7</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-subarray-min-product](https://leetcode.cn/problems/maximum-subarray-min-product/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-subarray-min-product](https://leetcode.cn/problems/maximum-subarray-min-product/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,2]', '[2,3,3,1,2]', '[3,1,5,6,4,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        def get_max(nums, l, r):\n",
    "            if l == r:\n",
    "                return nums[l] ** 2\n",
    "            if l == r - 1:\n",
    "                return max(max(nums[l], nums[r]), min(nums[l], nums[r]) * (nums[l] + nums[r]))\n",
    "            mid = (l + r) // 2\n",
    "            i = mid\n",
    "            j = mid + 1\n",
    "            res = 0\n",
    "            min_v = max(nums[mid], nums[mid + 1])\n",
    "            sv = 0\n",
    "            while i >= l and j <= r:\n",
    "                if nums[j] > nums[i]:\n",
    "                    sv += nums[j]\n",
    "                    if nums[j] < min_v:\n",
    "                        min_v = nums[j]\n",
    "                    j += 1\n",
    "                elif nums[j] < nums[i]:\n",
    "                    sv += nums[i]\n",
    "                    if nums[i] < min_v:\n",
    "                        min_v = nums[i]\n",
    "                    i -= 1\n",
    "                else:\n",
    "                    sv += nums[i] + nums[j]\n",
    "                    if nums[i] < min_v:\n",
    "                        min_v = nums[i]\n",
    "                    i -= 1\n",
    "                    j += 1\n",
    "                res = max(res, min_v * sv)\n",
    "            while i >= l:\n",
    "                sv += nums[i]\n",
    "                if nums[i] < min_v:\n",
    "                    min_v = nums[i]\n",
    "                i -= 1\n",
    "                res = max(res, min_v * sv)\n",
    "            while j <= r:\n",
    "                sv += nums[j]\n",
    "                if nums[j] < min_v:\n",
    "                    min_v = nums[j]\n",
    "                j += 1\n",
    "                res = max(res, min_v * sv)\n",
    "            \n",
    "            return max(res, get_max(nums, l, mid), get_max(nums, mid + 1, r))\n",
    "        \n",
    "        return get_max(nums, 0, len(nums) - 1) % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        nums.append(float('-inf'))\n",
    "        ans = 0\n",
    "        inc_stack = []\n",
    "        for num in nums:\n",
    "            suffix_sum = 0\n",
    "            while inc_stack and inc_stack[-1][0] > num:\n",
    "                top_num, sub_suffix_sum = inc_stack.pop()\n",
    "                suffix_sum += sub_suffix_sum\n",
    "                ans = max(ans, top_num * suffix_sum)\n",
    "            inc_stack.append((num, suffix_sum + num))\n",
    "            \n",
    "        return ans % (10**9+7)\n",
    "\n",
    "            \n",
    "\n",
    "# (3) 1 2 (5 6) 4\n",
    "\n",
    "# 5 6 7 8 4\n",
    "\n",
    "# suffix sum\n",
    "# 8 = 64\n",
    "# 8 7 = 105\n",
    "# 8 7 6 = 122\n",
    "# 8 7 6 5 = 130\n",
    "# 8 7 6 5 4 = 120\n",
    "\n",
    "# 4        = 16\n",
    "# 4 3      = 36 -> right mid\n",
    "# 4 3 2    = 18\n",
    "# 4 3 2 1  = 10\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        stack, presSum, res = [[nums[0], 0]], nums[0], 0\n",
    "        for x in nums[1:]:\n",
    "            last = presSum\n",
    "            while stack and x < stack[-1][0]:\n",
    "                pres = stack.pop()\n",
    "                res, last = max(res, (presSum - pres[1]) * pres[0]), pres[1]\n",
    "            if not stack or x > stack[-1][0]:\n",
    "                stack.append([x, last])\n",
    "            presSum += x\n",
    "        return max(res, max((presSum - x[1]) * x[0] for x in stack)) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        Input: nums = [1,2,3,2]\n",
    "        Output: 14\n",
    "        Explanation: The maximum min-product is achieved with the subarray [2,3,2] (minimum value is 2).\n",
    "        2 * (2+3+2) = 2 * 7 = 14.\n",
    "        we need to calculate the presum of subarray first, and use the effect range of minimum \n",
    "        value by using a mono stack \n",
    "        \"\"\"\n",
    "        # deal with the prefix sum part \n",
    "        pre = [0] * (len(nums) + 1)  # add sentinel\n",
    "        for i in range(1, len(nums)+1):\n",
    "            pre[i] = pre[i-1] + nums[i-1]  # calculate prefix sum \n",
    "\n",
    "        monoStack = [-1]\n",
    "        maxSumMin = float('-inf')\n",
    "\n",
    "        for i, j in enumerate(nums + [float('-inf')]):  # add sentinel trick \n",
    "            while len(monoStack)>1 and (nums[monoStack[-1]] > j):\n",
    "                prev_i = monoStack.pop()\n",
    "                right = i \n",
    "                left = monoStack[-1] + 1  # since we add a sentinal for the presum \n",
    "                maxSumMin = max(\n",
    "                    (pre[right] - pre[left]) * nums[prev_i],\n",
    "                    maxSumMin)\n",
    "\n",
    "            monoStack.append(i)\n",
    "        return maxSumMin % (10**9 + 7)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        pre_fix = [0]\n",
    "        for n in nums:\n",
    "            pre_fix.append(pre_fix[-1] + n)\n",
    "        s = []\n",
    "        res = 0\n",
    "        for i, n in enumerate(nums):\n",
    "            start_i = i\n",
    "            while s and n < s[-1][1]:\n",
    "                s_i, s_n = s.pop()\n",
    "                res = max(res, (pre_fix[i]-pre_fix[s_i]) * s_n)\n",
    "                start_i = s_i\n",
    "            s.append([start_i, n])\n",
    "            \n",
    "        for i, n in s:\n",
    "            res = max(res, (pre_fix[len(nums)]-pre_fix[i]) * n)\n",
    "        return res % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        nums = [0] + nums + [0]\n",
    "        pre_sum = [0] * (len(nums) + 1)\n",
    "        for i in range(len(nums)):\n",
    "            pre_sum[i + 1] = pre_sum[i] + nums[i]\n",
    "        stack = collections.deque()\n",
    "        result = 0\n",
    "        for i, v in enumerate(nums):\n",
    "            while len(stack) != 0 and v < nums[stack[-1]]:\n",
    "                idx = stack.pop()\n",
    "                min_prod = (pre_sum[i] - pre_sum[stack[-1] + 1]) * nums[idx]\n",
    "                result = max(result, min_prod)\n",
    "            stack.append(i)\n",
    "        \n",
    "        return result % (int(math.pow(10, 9)) + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        nums = [0] + nums + [0]\n",
    "        prefix_sum = list(accumulate(nums))\n",
    "        stack = []\n",
    "        res = 0\n",
    "\n",
    "        for idx, num in enumerate(nums):\n",
    "            while stack and num < nums[stack[-1]]:\n",
    "                cur = stack.pop()\n",
    "                itvl_sum = prefix_sum[idx-1] - prefix_sum[stack[-1]]\n",
    "                res = max(res, nums[cur] * itvl_sum)\n",
    "            stack.append(idx)\n",
    "\n",
    "        return res % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        nums = [0] + nums + [0]\n",
    "        prefix_sum = list(accumulate(nums))\n",
    "        stack = []\n",
    "        res = 0\n",
    "\n",
    "        for idx, num in enumerate(nums):\n",
    "            while stack and num < nums[stack[-1]]:\n",
    "                cur = stack.pop()\n",
    "                itvl_sum = prefix_sum[idx-1] - prefix_sum[stack[-1]]\n",
    "                res = max(res, nums[cur] * itvl_sum)\n",
    "            stack.append(idx)\n",
    "\n",
    "        return res % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        pre_sum = [0]\n",
    "        for i in range(len(nums)):\n",
    "            pre_sum.append(nums[i] + pre_sum[i])\n",
    "        res = 0\n",
    "        nums = [-inf] + nums + [-inf]\n",
    "        stack = []\n",
    "        for r, n in enumerate(nums):\n",
    "            while stack and nums[stack[-1]] > n:\n",
    "                i = stack.pop()\n",
    "                # print(nums[i])\n",
    "                # print(nums[stack[-1]:r])\n",
    "                cur = nums[i] * (pre_sum[r - 1] - pre_sum[stack[-1]])  # 注意left+1\n",
    "                res = max(res, cur)\n",
    "            stack.append(r)\n",
    "        return res % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        mod=10**9 + 7\n",
    "        nums=[0]+nums+[0]\n",
    "        n=len(nums)\n",
    "        pre=[0]*n\n",
    "        for i in range(1,n):\n",
    "            pre[i]=pre[i-1]+nums[i]\n",
    "        ans=0\n",
    "        st=[-1]\n",
    "        for k,v in enumerate(nums):\n",
    "            while st and nums[st[-1]]>v:\n",
    "                idx=st.pop()\n",
    "                cur=(pre[k-1]-(pre[st[-1]]))*nums[idx]\n",
    "                ans=max(ans,cur)\n",
    "            st.append(k)\n",
    "        return ans%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        pre = [0]\n",
    "        for x in nums:\n",
    "            pre.append(pre[-1]+x)\n",
    "\n",
    "        nums = [float('-inf')] + nums + [float('-inf')]\n",
    "        stack = []\n",
    "        res = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            while stack and x < nums[stack[-1]]:\n",
    "                res = max(res, nums[stack[-1]]*(pre[i-1]-pre[stack[-2]]))\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        return res % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        mono_stack, nums = [], [-1] + nums + [-1]\n",
    "        preSum = [nums[0]]\n",
    "        # 计算和，减少运算时间\n",
    "        for num in nums[1:]:\n",
    "            preSum.append(preSum[-1] + num)\n",
    "        ans = 0\n",
    "        \n",
    "        for i, num in enumerate(nums):\n",
    "            while mono_stack and num < nums[mono_stack[-1]]:\n",
    "                j = mono_stack.pop()\n",
    "                k = mono_stack[-1]\n",
    "                # 从k+1到i-1这部分区间使得nums[j]在区间内保证最小\n",
    "                # preSum[i] - preSum[k]是k+1 ~ i-1区间的和\n",
    "                ans = max(ans, nums[j] * (preSum[i-1] - preSum[k]))\n",
    "            mono_stack.append(i)\n",
    "        \n",
    "        return ans % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        \n",
    "        summ = 0\n",
    "        presum = [0]\n",
    "        for num in nums:\n",
    "            summ += num\n",
    "            presum.append(summ)\n",
    "        \n",
    "        stack = []\n",
    "        result = -float('inf')\n",
    "        nums = [-float('inf')] + nums[:] + [-float('inf')]\n",
    "        for i, num in enumerate(nums):\n",
    "            while stack and nums[stack[-1]] >= num:\n",
    "                popIndex = stack.pop()\n",
    "                if not stack:\n",
    "                    return result % MOD\n",
    "                result = max(result, nums[popIndex] * (presum[i-1] - presum[stack[-1]]))\n",
    "            stack.append(i)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        nums = [0] + nums + [0]\n",
    "        presum = [0] + list(accumulate(nums))\n",
    "        stack = []  # 单调递增栈\n",
    "        res = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            while stack and num < nums[stack[-1]]:\n",
    "                idx = stack.pop()\n",
    "                l, r = stack[-1] + 1, i - 1\n",
    "                res = max(res, nums[idx] * (presum[r + 1] - presum[l]))\n",
    "            stack.append(i)\n",
    "        return res % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        单调栈. O(N).\n",
    "\n",
    "        思路: 依次遍历所有下标 i, 找到以下标 i 为最小值的最长子数组, 更新最小乘积.\n",
    "        即: 从 i 往两边扩, 两边分别找到第一个比 nums[i] 小的数.\n",
    "        \"\"\"\n",
    "        presum = []\n",
    "        for num in nums:\n",
    "            presum.append(presum[-1] + num if presum else num)\n",
    "        presum += [0]\n",
    "\n",
    "        ans = -float(\"inf\")\n",
    "        stack: List[List[int]] = []\n",
    "        for i in range(len(nums)):\n",
    "            while stack:\n",
    "                if nums[stack[-1][0]] == nums[i]:\n",
    "                    stack[-1].append(i)\n",
    "                    break\n",
    "                elif nums[stack[-1][0]] > nums[i]:\n",
    "                    j = stack.pop()[0]\n",
    "                    # 求以 nums[j] 为最小值的子数组的最小乘积最大值\n",
    "                    # 先求左边第一个比 nums[j] 小的数\n",
    "                    L = -1  # 默认它左边没有比它小的数\n",
    "                    if stack:  # 它的左边存在比它小的数\n",
    "                        L = stack[-1][-1]\n",
    "                    # 再求右边第一个比 nums[j] 小的数\n",
    "                    ans = max(ans, nums[j] * (presum[i - 1] - presum[L]))\n",
    "                else:\n",
    "                    break\n",
    "            stack.append([i])\n",
    "\n",
    "        # 最后结算stack中的下标 (它们右侧都没有比它小的数)\n",
    "        while stack:\n",
    "            j = stack.pop()[0]\n",
    "            L = -1\n",
    "            if stack:\n",
    "                L = stack[-1][-1]\n",
    "            ans = max(ans, nums[j] * (presum[len(nums) - 1] - presum[L]))\n",
    "\n",
    "        return ans % ((10 ** 9) + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        # find each num as the min of the subarray, the longest subarray(because all num is positive, so it is also the largest sum) can get\n",
    "        # find each num, the pre nearest smaller num and the next nearest not larger num\n",
    "        st = [] # increase stack\n",
    "        pre = [0]\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        nums.append(0)\n",
    "        left, right = [-1] * n, [n] * n\n",
    "        for i, v in enumerate(nums):\n",
    "            pre.append(pre[i] + nums[i])\n",
    "            while st and nums[st[-1]] >= v: # the stack top num find the right nearest not larger num\n",
    "                t = st.pop()\n",
    "                ans = max(ans, nums[t] * (pre[i] - pre[left[t] + 1]))\n",
    "            if st: left[i] = st[-1]\n",
    "            st.append(i)\n",
    "        return ans % (10 ** 9 + 7)\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "\n",
    "MAX_INT64 = sys.maxsize\n",
    "MIN_INT64 = -sys.maxsize - 1\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        arr = nums\n",
    "        size = len(arr)\n",
    "\n",
    "        # 获得前缀数组和\n",
    "        sums = [None for i in range(size)]\n",
    "        sums[0] = arr[0]\n",
    "        for i in range(1, size):\n",
    "            sums[i] = sums[i - 1] + arr[i]\n",
    "\n",
    "        # 最小值所在最大区间\n",
    "        maxValue = MIN_INT64\n",
    "        # 这里用一个数组来实现栈，会快\n",
    "        stack = [None for i in range(size)]\n",
    "        # 用一个变量，来记录栈的大小\n",
    "        stackSize = 0\n",
    "\n",
    "        for i in range(size):\n",
    "            # 弹出时\n",
    "            #                                                当值相等的时候，也弹出\n",
    "            while stackSize!= 0 and arr[stack[stackSize - 1]] >= arr[i]:\n",
    "                # 弹出\n",
    "                # 注意，这里最后一个的值是大小 - 1\n",
    "                stackSize -= 1\n",
    "                j = stack[stackSize]\n",
    "                # 左边界\n",
    "                #           左边界为空的时候，则区间和为右边界i - 1的sums值\n",
    "                #           左边界不为空，则区间为[stack.queue[-1] + 1, i - 1]\n",
    "                #              则区间和为sums[i - 1] - sums[stack.queue[-1] + 1 - 1]\n",
    "                sumValue = sums[i - 1] if stackSize == 0 else (sums[i - 1] - sums[stack[stackSize - 1]])\n",
    "                # 结果的处理\n",
    "                maxValue = max(maxValue, sumValue * arr[j])\n",
    "            # 压入时\n",
    "            stack[stackSize] = i\n",
    "            stackSize += 1\n",
    "        # 清空剩余栈\n",
    "        while stackSize != 0:\n",
    "            stackSize -= 1\n",
    "            j = stack[stackSize]\n",
    "            # 左边界\n",
    "            # leftIndex = -1 if stack.empty() else stack.queue[-1]\n",
    "            # 右边界肯定为-1\n",
    "            # 区间和\n",
    "            #          左边界为-1,右边界为-1，则肯定区间和为sums[size - 1]\n",
    "            #                                    左边界不是-1，则[stack.queue[-1] + 1, -1]\n",
    "            #                                      则和为sums[size - 1] - sums[stack.queue[-1] + 1 - 1]\n",
    "            sumValue = sums[size - 1] if stackSize == 0 else (sums[size - 1] - sums[stack[stackSize - 1]])\n",
    "            # 结果处理\n",
    "            maxValue = max(maxValue, sumValue * arr[j])\n",
    "        \n",
    "        # leetcode中要求结果取余操作\n",
    "        return int(maxValue % 1000000007)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        nums.append(0)\n",
    "        s,st,res = [0]*(len(nums)+1),[],0\n",
    "        for i,v in enumerate(nums):\n",
    "            s[i+1] = s[i]+v\n",
    "            while st and nums[st[-1]]>=v:\n",
    "                idx = st.pop()#!!!这个数作为最小\n",
    "                left = st[-1] if st else -1\n",
    "                res = max(res,(s[i]-s[left+1])*nums[idx])\n",
    "            st.append(i)\n",
    "        return res%(10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        nums.append(1)\n",
    "        s, st, res = [0] * (len(nums) + 1), [], 0\n",
    "        for i, v in enumerate(nums):\n",
    "            s[i+1] = s[i] + v\n",
    "            while st and nums[st[-1]] >= v:\n",
    "                idx = st.pop()\n",
    "                left = st[-1] if st else -1\n",
    "                res = max(res, (s[i] - s[left+1])*nums[idx])\n",
    "            st.append(i)\n",
    "        return res % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        n, res = len(nums), 0\n",
    "        ls = [-1] * n\n",
    "        rs = [n] * n\n",
    "        stk = list()\n",
    "        # 依次遍历找到l, r, 满足nums[l] < nums[i], nums[i] >= nums[r]\n",
    "        for i in range(n):\n",
    "            while stk and nums[stk[-1]] >= nums[i]:\n",
    "                rs[stk.pop()] = i\n",
    "            if stk: ls[i] = stk[-1]\n",
    "            stk.append(i)\n",
    "        pref = list(itertools.accumulate(nums, initial=0))\n",
    "        MOD = 10 ** 9 + 7\n",
    "        for i in range(n):\n",
    "            cur = nums[i] * (pref[rs[i]] - pref[ls[i]+1])\n",
    "            res = cur if cur > res else res\n",
    "        return res % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        ans = nums[0]\n",
    "        pre_sum = list(itertools.accumulate(nums))\n",
    "        stack = []\n",
    "        for i, it in enumerate(nums):\n",
    "            index = i\n",
    "            while stack and stack[-1][1] > it:\n",
    "                j, j_num = stack.pop()\n",
    "                ans = max(ans, j_num * (pre_sum[i - 1] - pre_sum[j] + nums[j]))\n",
    "                index = j\n",
    "            stack.append((index, it))\n",
    "        for i, it in stack:\n",
    "            ans = max(ans, it * (pre_sum[-1] - pre_sum[i] + nums[i]))\n",
    "        return ans % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        nums = [0] + nums + [0]\n",
    "        stack = []\n",
    "        index = 0\n",
    "        li = [0] * len(nums)\n",
    "        while index < len(nums):\n",
    "            if index > 0:\n",
    "                li[index] = li[index-1] + nums[index]\n",
    "            while stack and nums[stack[-1]] > nums[index]:\n",
    "                tmp = stack.pop()\n",
    "                res = max(res, nums[tmp]*(li[index-1]-li[stack[-1]]))\n",
    "            stack.append(index)\n",
    "            index += 1\n",
    "        return res % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        nums.append(0)\n",
    "        n,ans=len(nums),0\n",
    "        pre,stk=[0]*(n+1),[-1]\n",
    "        for i in range(n):\n",
    "            pre[i+1]=pre[i]+nums[i]\n",
    "        for i in range(n):\n",
    "            while len(stk)>1 and nums[stk[-1]]>nums[i]:\n",
    "                x=stk.pop()\n",
    "                a=(pre[i]-pre[stk[-1]+1])*nums[x]\n",
    "                if a>ans:\n",
    "                    ans=a\n",
    "            stk.append(i)\n",
    "        return ans%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        # 数组和  前缀和\n",
    "        \n",
    "        stk = []\n",
    "        ans = -inf\n",
    "        MOD = 10**9 +7\n",
    "        nums = [0] + nums + [0]\n",
    "        presums = list(accumulate(nums,initial = 0))\n",
    "        # print(presums)\n",
    "        for r,x in enumerate(nums):\n",
    "            while len(stk) > 1 and nums[stk[-1]] >= x:\n",
    "                idx = stk.pop()\n",
    "                # print(nums[idx],presums[r],presums[stk[-1]])\n",
    "                ans = max(ans, nums[idx] * (presums[r]- presums[stk[-1]+1]))\n",
    "                # print(ans)\n",
    "            stk.append(r)\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        nums.append(1)\n",
    "        s,st,res = [0]*(len(nums)+1),[],0\n",
    "        for i,v in enumerate(nums):\n",
    "            s[i+1] = s[i]+v\n",
    "            while st and nums[st[-1]]>=v:\n",
    "                idx = st.pop()#!!!这个数作为最小\n",
    "                left = st[-1] if st else -1\n",
    "                res = max(res,(s[i]-s[left+1])*nums[idx])\n",
    "            st.append(i)\n",
    "        return res%(10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        nums.append(1)\n",
    "        s,st,res = [0]*(len(nums)+1),[],0\n",
    "        for i,v in enumerate(nums):\n",
    "            s[i+1] = s[i]+v\n",
    "            while st and nums[st[-1]]>=v:\n",
    "                idx = st.pop()#!!!这个数作为最小\n",
    "                left = st[-1] if st else -1\n",
    "                res = max(res,(s[i]-s[left+1])*nums[idx])\n",
    "            st.append(i)\n",
    "        return res%(10**9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        #前缀和\n",
    "        sum = [0]\n",
    "        for num in nums:\n",
    "            sum.append(sum[-1]+num)\n",
    "        n = len(nums)\n",
    "        #枚举每个数，用两个单调栈，当作最小值找左右边界，向左找第一个小于的，向右找第一个小于的\n",
    "        stack = [-1]\n",
    "        ans = 0\n",
    "        for i,num in enumerate(nums+[-inf]):\n",
    "            while len(stack)>1 and nums[stack[-1]]>num:\n",
    "                tmp = stack.pop()\n",
    "                ans = max(ans, nums[tmp]*(sum[i]-sum[stack[-1]+1])) \n",
    "            stack.append(i)\n",
    "        return ans%(10**9 + 7)\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        \n",
    "        \"\"\"\n",
    "        這題真的超難\n",
    "        \n",
    "        1. 一個 array 的 min-product 是指這個 array 的最小元素 x array 的總和\n",
    "        2. 給一個 array: nums, 在這個 array 裡面找到一個 subarray\n",
    "           可以最大化 min-product, 把結果取 mod (10^9 + 7) 並回傳\n",
    "           (subarray 是 nums 連續的一部分)\n",
    "           \n",
    "        想法1. 暴力法: O(n^2)\n",
    "        每個元素都掃過一次, 每個元素都把所有對應的 subarray 找出來, 計算 min-product\n",
    "        \n",
    "        想法2. Monotonic increasing stack: O(n)\n",
    "        \n",
    "            a. 掃過 nums 每個元素\n",
    "               把每個元素對應的 index, value 用 \"升序\" 的形式加入到 stack\n",
    "               \n",
    "               這是確保:\n",
    "               a-1. 每個元素都是 subarray 的 \"min\" (可以找到 min)\n",
    "               a-2. 升序可以讓 subarray 盡可能的大, \"sum\" 也會變大\n",
    "                    也就是讓 subarray \"往右擴展\"\n",
    "                    \n",
    "            b. 如果當前的數字比 stack[-1] 還要小, 代表 min 有更小的了\n",
    "               這時要把 stack[-1] 踢掉, 踢掉那瞬間要把踢掉的元素視為一個 subarray 計算 min-product\n",
    "               並且把 \"當前數字\" 對應的 index \"往左擴展\" 到 pop 出來的 index (讓 sum 變大)\n",
    "               這也是一個 subarray, 例如: [1, 2, 3, 2] 的 [3, 2]\n",
    "        \"\"\"\n",
    "        result = 0\n",
    "        stack  = []  # pair: [index, value]\n",
    "        prefix = [0] # 計算 nums 裡面每個 prefix 的總和, 之後計算任意的 subarray 可以比較快算出 sum\n",
    "        \n",
    "        \"\"\"\n",
    "        nums = [1, 2, 3, 4]\n",
    "        prefix[0] = 1          ; sum([1])\n",
    "        prefix[1] = 1 + 2 = 3  ; sum([1, 2])\n",
    "        prefix[2] = 3 + 3 = 6  ; sum([1, 2, 3])\n",
    "        prefix[3] = 6 + 4 = 10 ; sum([1, 2, 3, 4])\n",
    "        \"\"\"\n",
    "        for n in nums:\n",
    "            prefix.append(prefix[-1] + n)\n",
    "        #print(prefix)\n",
    "            \n",
    "        for i, n in enumerate(nums):\n",
    "            new_start = i # 每個元素都可以是 subarray 的起點, 也期望他的數值是 subarray 的最小值\n",
    "            while stack and n < stack[-1][1]: # 出現 decreasing order 了\n",
    "                start, value = stack.pop() # 把 stack 最上層踢出來, 我們要維持 increasing order\n",
    "                \n",
    "                # 把 stack 彈出來時, 也要把踢掉的元素視為一個 subarray\n",
    "                \"\"\"\n",
    "                假設: [1, 2, 3, 2], i = 3, start = 2\n",
    "                prefix[0] = 0\n",
    "                prefix[1] = 1\n",
    "                prefix[2] = 1 + 2         = 3 (start = 2)\n",
    "                prefix[3] = 1 + 2 + 3     = 6 (i = 3)\n",
    "                prefix[4] = 1 + 2 + 3 + 2 = 8\n",
    "                prefix[i]: 到 i 之前, 但是不包含 nums[i] 的 nums 總和\n",
    "                \"\"\"\n",
    "                total  = prefix[i] - prefix[start]  # start ~ i 之間的 sum\n",
    "                result = max(result, value * total) # 單獨抽出的 subarray 計算 min-product\n",
    "                new_start = start # 當前的元素就要把 index \"往左擴展\" 到 pop 出來的 \"那個index\"\n",
    "                \n",
    "            # 把新掃到的元素加入 stack\n",
    "            stack.append([new_start, n])\n",
    "        \n",
    "        # 掃過整個 stack\n",
    "        for start, value in stack:\n",
    "            # 從 start ~ nums 尾端的 subarray 總和\n",
    "            total  = prefix[len(nums)] - prefix[start] # 對於 stack 的 start, end 都是 nums 的最尾端\n",
    "            result = max(result, value * total)\n",
    "            \n",
    "        return result % (10**9 + 7) # 結果要記得取 mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        # 单调递增栈\n",
    "        n = len(nums)\n",
    "        sums = [0] * n\n",
    "        sums[0] = nums[0]\n",
    "        for i in range(1, n):\n",
    "            sums[i] = sums[i - 1] + nums[i]\n",
    "        stack = []\n",
    "        res = -sys.maxsize - 1\n",
    "\n",
    "        for i in range(n):\n",
    "            while stack and nums[stack[-1]] >= nums[i]:\n",
    "                j = stack.pop()\n",
    "                total = sums[i - 1] if not stack else sums[i - 1] - sums[stack[-1]]\n",
    "                res = max(res, total * nums[j])\n",
    "\n",
    "            stack.append(i)\n",
    "\n",
    "        while stack:\n",
    "            j = stack.pop()\n",
    "            total = sums[n - 1] if not stack else sums[n - 1] - sums[stack[-1]]\n",
    "            res = max(res, total * nums[j])\n",
    "        \n",
    "        return res % 1000000007\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, arr: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(arr)\n",
    "        acc = list(accumulate(arr))\n",
    "        def fun(i, j):\n",
    "            lev = 0 if i == 1 else acc[i - 2]\n",
    "            return acc[j - 1] - lev\n",
    "        arr = [-inf] + arr + [-inf]\n",
    "        st = [0]\n",
    "        res = -inf\n",
    "\n",
    "        for i in range(1, n + 2): \n",
    "            while arr[i] < arr[st[-1]]:\n",
    "                j = st.pop()\n",
    "                a = fun(st[-1] + 1, i - 1) * arr[j]\n",
    "                res = max(res, a)\n",
    "            st.append(i)\n",
    "        return res % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        a = [0] + nums+ [0]\n",
    "        P = list(accumulate(a,initial = 0))\n",
    "        ans= 0\n",
    "        stk = []\n",
    "        for i in range(len(a)):\n",
    "            v = a[i]\n",
    "            while stk and a[stk[-1]] > v:\n",
    "                base = stk.pop()\n",
    "                if stk:\n",
    "                    left = stk[-1]\n",
    "                    ans = max(ans,a[base] * (P[i]-P[left+1]) )\n",
    "\n",
    "            stk.append(i)    \n",
    "        return ans % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        nums = [0] + nums + [0]\n",
    "        n = len(nums)\n",
    "        pre_sum = [0] * n\n",
    "        res = 0\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            pre_sum[i] = pre_sum[i-1] + nums[i]\n",
    "            while stack and nums[stack[-1]] > nums[i]:\n",
    "                idx = stack.pop()\n",
    "                res = max(res, (pre_sum[i-1]-pre_sum[stack[-1]])*nums[idx])\n",
    "            stack.append(i)\n",
    "        return res % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        nums.append(0)\n",
    "        pre = list(itertools.accumulate(nums, initial=0))\n",
    "        st = []\n",
    "        ans = 0\n",
    "        for i, n in enumerate(nums):\n",
    "            while st and nums[st[-1]] > n:\n",
    "                m, l, r = st.pop(), st[-1] if st else -1, i\n",
    "                s = pre[r] - pre[l + 1]\n",
    "                ans = max(ans, nums[m] * s)\n",
    "            st.append(i)\n",
    "        return ans % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        n      = len(nums)\n",
    "        answer = -float('inf')\n",
    "        preSum = list(accumulate(nums, initial = 0))\n",
    "        st     = [] # 单调\n",
    "        # print(preSum)\n",
    "\n",
    "        # 方法一\n",
    "        for j, v in enumerate(nums + [-sys.maxsize]):\n",
    "            while st and nums[st[-1]] > v: # 单调递增\n",
    "                i = st.pop() # R = j\n",
    "                L = st[-1] if st else -1 #[L, R) # 当栈为空时候，代表当前左侧没有比当前更小的元素，所以没法向左扩展\n",
    "                # 计算贡献 nums[i] 是区间[L, R) 的最小值 （R - L）* nums[i]\n",
    "                answer = max(answer, nums[i] * (preSum[j] - preSum[L + 1]))\n",
    "\n",
    "            st.append(j) \n",
    "        \n",
    "        # 方法二\n",
    "        # L, R = [-1] * n, [+n] * n\n",
    "        # for i, v in enumerate(nums):\n",
    "        #     while st and nums[st[-1]] >= v: # 单调递增\n",
    "        #         R[st.pop()] = i\n",
    "        #     if st:\n",
    "        #         L[i] = st[-1]\n",
    "        #     st.append(i)\n",
    "\n",
    "        # answer = max((preSum[R[i]] - preSum[L[i] + 1]) * nums[i] for i in range(n))\n",
    "\n",
    "        return answer % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "\n",
    "        res = 0\n",
    "        # stack is going to be [index][value] pair\n",
    "        stack = []\n",
    "        prefix = [0]\n",
    "        for n in nums:\n",
    "            prefix.append(prefix[-1] + n)\n",
    "        \n",
    "        for i, n in enumerate(nums):\n",
    "            newstart = i\n",
    "            while stack and stack[-1][1] > n:\n",
    "                start,val = stack.pop()\n",
    "                total = prefix[i] - prefix[start]\n",
    "                res = max(res,val * total)\n",
    "                newstart = start\n",
    "\n",
    "            stack.append((newstart,n))\n",
    "\n",
    "        for start, val in stack:\n",
    "            total = prefix[len(nums)] - prefix[start]\n",
    "\n",
    "            res = max(res,val * total)\n",
    "\n",
    "        return res % (10**9 + 7)\n",
    "\n",
    "        # https://www.youtube.com/watch?v=YLesLbNkyjA&list=PLot-Xpze53lfxD6l5pAGvCD4nPvWKU8Qo&index=8&ab_channel=NeetCode\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        aux = [0] + nums+ [0]\n",
    "        n = len(nums)\n",
    "        m = len(aux)\n",
    "        # left[i] : the index of first number smaller than nums[i]\n",
    "        #             left[i].i\n",
    "        left = [0] * m\n",
    "        stk = []\n",
    "        P = [0]\n",
    "        for v in aux:\n",
    "            P.append((P[-1]+  v))\n",
    "        ans = 0\n",
    "        for i,v in enumerate(aux):\n",
    "            while stk and aux[stk[-1]] > v:\n",
    "                cur = stk.pop()\n",
    "                if stk:\n",
    "                    pre = stk[-1]\n",
    "                    ans = max(ans, (P[i]-P[pre+1]) * aux[cur])\n",
    "            stk.append(i)    \n",
    "        return ans % MOD\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        s = list(accumulate(nums, initial = 0))\n",
    "        n = len(nums)\n",
    "        # nums.append(-1)\n",
    "        st = []\n",
    "        left, right = [-1] * n, [n] * n\n",
    "        for i, x in enumerate(nums):\n",
    "            while st and nums[st[-1]] >= x:\n",
    "                right[st.pop()] = i\n",
    "            \n",
    "            if st:\n",
    "                left[i] = st[-1]\n",
    "            st.append(i)\n",
    "\n",
    "\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            res = max(res, nums[i] * (s[right[i]] - s[left[i]+1]))\n",
    "            # print(left[i], i, right[i])\n",
    "\n",
    "        return res % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        M = 10**9 + 7\n",
    "        n = len(nums)\n",
    "        left = [-1] * n\n",
    "        st = []\n",
    "        for i,v in enumerate(nums):\n",
    "            while st and v <= nums[st[-1]]:\n",
    "                st.pop()\n",
    "            if st:\n",
    "                left[i] = st[-1]\n",
    "            st.append(i)\n",
    "        s = list(accumulate(nums, initial=0))\n",
    "        ans = 0\n",
    "        st = []\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while st and nums[i] <= nums[st[-1]]:\n",
    "                st.pop()\n",
    "            r = st[-1] if st else n\n",
    "            st.append(i)\n",
    "            ans = max(ans, nums[i] * (s[r] - s[left[i]+1]))\n",
    "\n",
    "        return ans % M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        left = [-1] * n\n",
    "        right = [n] * n\n",
    "        st = [-1]\n",
    "        mod = 10 ** 9 + 7\n",
    "        for i, num in enumerate(nums):\n",
    "            while st[-1] != -1 and nums[st[-1]] >= num:\n",
    "                st.pop()\n",
    "            left[i] = st[-1]\n",
    "            st.append(i)\n",
    "        st = [n]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while st[-1] != n and nums[st[-1]] >= nums[i]:\n",
    "                st.pop()\n",
    "            right[i] = st[-1]\n",
    "            st.append(i)\n",
    "        acc = list(accumulate(nums, initial=0))\n",
    "        ans = -1\n",
    "        for i,num in enumerate(nums):\n",
    "            res = num * (acc[right[i]]-acc[left[i]+1])\n",
    "            ans = max(ans, res)\n",
    "        return ans % mod\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        pre = [0] + [x for x in accumulate(nums)]\n",
    "        ans, st = 0, [-1]\n",
    "        for i, x in enumerate(nums + [0]):\n",
    "            while len(st) > 1 and nums[st[-1]] > x:\n",
    "                j = st.pop()\n",
    "                ans = max(ans, nums[j] * (pre[i] - pre[st[-1] + 1]))\n",
    "            st.append(i)\n",
    "        return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        nums.append(-1)\n",
    "        mod=10**9+7\n",
    "        res=0\n",
    "        stk=[]\n",
    "        pre=[0]*len(nums)\n",
    "        prefix=[0]\n",
    "        for n in nums:\n",
    "            prefix.append(prefix[-1]+n)\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            while stk and nums[i]<=nums[stk[-1]]:\n",
    "                top=stk.pop()\n",
    "                res=max(res,nums[top]*(prefix[i]-prefix[pre[top]+1]))\n",
    "            pre[i]=-1 if not stk else stk[-1]\n",
    "            stk.append(i)\n",
    "        return res%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        left = [-1] * n\n",
    "        right = [n] * n\n",
    "        a = []\n",
    "        for i in range(n):\n",
    "            while a and nums[a[-1]] >= nums[i]:\n",
    "                right[a[-1]] = i\n",
    "                a.pop()\n",
    "            if a:\n",
    "                left[i] = a[-1]\n",
    "            a.append(i)\n",
    "        ans = 0\n",
    "        presum = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            presum[i + 1] = presum[i] + nums[i]\n",
    "        # 求和[left[i] + 1, right[i] - 1]\n",
    "        for i in range(n):\n",
    "            ans = max(ans, nums[i] * (presum[right[i]] - presum[left[i] + 1]))\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, arr: List[int]) -> int:\n",
    "        pre = [0]\n",
    "        for i, v in enumerate(arr):\n",
    "            pre.append(pre[i] + v)\n",
    "\n",
    "        n = len(arr)\n",
    "        left, right, st = [-1] * n, [n] * n, []\n",
    "        for i, x in enumerate(arr):\n",
    "            while st and arr[st[-1]] >= x:\n",
    "                right[st.pop()] = i\n",
    "            if st: left[i] = st[-1]\n",
    "            st.append(i)\n",
    "        # print(pre, left, right, arr)\n",
    "        ans = 0\n",
    "        for n, L, R in zip(arr, left, right):\n",
    "            ans = max(ans, n * (pre[R] - pre[L + 1]))\n",
    "        return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        MOD=10**9+7\n",
    "        stack=[]\n",
    "        n=len(nums)\n",
    "        left=[-1]*n\n",
    "        right=[n]*n\n",
    "        for i in range(n):\n",
    "            while stack and nums[stack[-1]]>=nums[i]:\n",
    "                j=stack.pop()\n",
    "                right[j]=i\n",
    "            if stack:\n",
    "                left[i]=stack[-1]\n",
    "            stack.append(i)\n",
    "        presum=list(accumulate(nums,initial=0))\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            t=nums[i]*(presum[right[i]]-presum[left[i]+1])\n",
    "            ans=max(ans,t)\n",
    "        return ans%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        mod = (10**9 + 7)\n",
    "        n = len(nums)\n",
    "        left, right = [-1]*n, [n]*n\n",
    "        # 单调栈\n",
    "        stack = deque([])\n",
    "        for i in range(n):\n",
    "            while stack and nums[i]<=nums[stack[-1]]:\n",
    "                right[stack[-1]]=i\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                left[i]=stack[-1]\n",
    "            stack.append(i)\n",
    "        \n",
    "        # 前缀和\n",
    "        pre = [0]*(n+1)\n",
    "        for i in range(n):\n",
    "            pre[i+1]=pre[i]+nums[i]\n",
    "        \n",
    "        # 求结果\n",
    "        ans = 0\n",
    "    \n",
    "        for i in range(n):\n",
    "            print(left[i], right[i])\n",
    "            ans = max(ans, nums[i]*(pre[right[i]]-pre[left[i]+1]))\n",
    "\n",
    "        return ans%mod\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        # 前缀和，+求每个数字左右小于它自己的index ,栈\n",
    "\n",
    "\n",
    "        # 递增栈\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        left = [0]*n\n",
    "        stack = [-1]\n",
    "        right = [n]*n\n",
    "        pre = [0]*(n+1)\n",
    "        for i,x in enumerate(nums):\n",
    "            pre[i+1] = pre[i]+nums[i]\n",
    "            while len(stack)>1 and x <= nums[stack[-1]]:\n",
    "                key = stack.pop()\n",
    "                right[key] = i\n",
    "            left[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        ans = 0\n",
    "        # stack = [n]\n",
    "        # for j in range(n-1,-1,-1):\n",
    "        #     x = nums[j]\n",
    "        #     while len(stack)>1 and x < nums[stack[-1]]:\n",
    "        #         stack.pop()\n",
    "        #     # print(stack)\n",
    "        #     right[j] = stack[-1]\n",
    "        #     stack.append(j)\n",
    "        # print(left,right)\n",
    "        for i in range(n):\n",
    "            ans = max(ans, nums[i]*(pre[right[i]] - pre[left[i]+1]))\n",
    "\n",
    "        return ans %(10**9+7)\n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9+7\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        pres = [0] * (n+1)\n",
    "        left = [-1] * n\n",
    "        right = [n] * n\n",
    "        stack = []\n",
    "        for i, x in enumerate(nums):\n",
    "            pres[i+1] = pres[i] + x\n",
    "            while stack and x < nums[stack[-1]]:\n",
    "                right[stack.pop()] = i\n",
    "            if stack:\n",
    "                left[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "\n",
    "        ans = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            l, r = left[i] + 1, right[i] - 1\n",
    "            ans = max(ans, x * (pres[r+1] - pres[l]))\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "      n = len(nums)\n",
    "      presum = [0] * n\n",
    "      presum[0] = nums[0]\n",
    "      for i in range(1, n):\n",
    "        presum[i] = presum[i - 1] + nums[i]\n",
    "\n",
    "      left = [0] * n\n",
    "      right = [0] * n\n",
    "      stk = [] # 栈中是还未找到比它值更小元素的元素\n",
    "      for i in range(n):\n",
    "        while stk and nums[stk[-1]] >= nums[i]:\n",
    "          right[stk.pop()] = i\n",
    "\n",
    "        if not stk:\n",
    "          left[i] = -1\n",
    "        else:\n",
    "          left[i] = stk[-1]\n",
    "\n",
    "        stk.append(i)\n",
    "\n",
    "      while stk:\n",
    "        right[stk.pop()] = n\n",
    "\n",
    "      ret = 0\n",
    "      for i in range(n):\n",
    "        l = left[i]\n",
    "        r = right[i]\n",
    "        if l != -1 and r != n:\n",
    "          ps = presum[r] - nums[r] - presum[l]\n",
    "        elif l == -1 and r == n:\n",
    "          ps = presum[r - 1]\n",
    "        elif l == -1:\n",
    "          ps = presum[r] - nums[r]\n",
    "        else:\n",
    "          ps = presum[r - 1] - presum[l]\n",
    "        ret = max(nums[i] * ps, ret)\n",
    "      return ret % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        mod = 1000000007\n",
    "        acc = list(accumulate(nums,initial=0))\n",
    "        n = len(nums)\n",
    "        st,left,right = [],[-1]*n,[n]*n\n",
    "        for i,x in enumerate(nums):\n",
    "            while st and nums[st[-1]] > x:\n",
    "                right[st.pop()] = i\n",
    "            if st: left[i] = st[-1]\n",
    "            st.append(i)\n",
    "        return max((acc[r]-acc[l+1])*x for l,r,x in zip(left,right,nums))%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        k = 10**9 + 7\n",
    "        n = len(nums)\n",
    "        total = [0]\n",
    "        q = []\n",
    "        right = [0] * n\n",
    "        left = [0] * n\n",
    "        for x in nums:\n",
    "            total.append(x + total[-1])\n",
    "        for i in range(n):\n",
    "            while q and nums[q[-1]] > nums[i]:\n",
    "                right[q.pop()] = i\n",
    "            q.append(i)\n",
    "        while q:\n",
    "            right[q.pop()] = n\n",
    "        for i in range(n - 1,-1,-1):\n",
    "            while q and nums[q[-1]] >= nums[i]:\n",
    "                left[q.pop()] = i\n",
    "            q.append(i)\n",
    "        while q:\n",
    "            left[q.pop()] = -1\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans,nums[i] * (total[right[i]] - total[left[i] + 1]))\n",
    "        return ans % k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        acc = list(accumulate(nums, initial=0))\n",
    "        s = [0] * n\n",
    "        st = []\n",
    "        ans = 0\n",
    "        for idx, i in enumerate(nums):\n",
    "            while st and nums[st[-1]] > i:\n",
    "                tidx = st.pop()\n",
    "                if (t:= nums[tidx] * (acc[idx]-acc[s[tidx]])) > ans:\n",
    "                    ans = t\n",
    "            if st:\n",
    "                s[idx] = st[-1] + 1\n",
    "            st.append(idx)\n",
    "        return max(ans, max(nums[i] * (acc[-1]-acc[s[i]]) for i in st)) % (10 ** 9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        left = [-1] * n\n",
    "        right = [n] * n\n",
    "        st = []\n",
    "        res = 0\n",
    "        MOD = 10**9 + 7\n",
    "        for i in range(0, n):\n",
    "            while st and nums[st[-1]] > nums[i]:\n",
    "                st.pop()\n",
    "            if st:\n",
    "                left[i] = st[-1]\n",
    "            st.append(i)\n",
    "        st = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while st and nums[st[-1]] >= nums[i]:\n",
    "                st.pop()\n",
    "            if st:\n",
    "                right[i] = st[-1]\n",
    "            st.append(i)\n",
    "        \n",
    "        temp = [0] * n\n",
    "        temp[0] = nums[0]\n",
    "        for i in range(1, n):\n",
    "            temp[i] = temp[i-1] + nums[i]\n",
    "\n",
    "        for i in range(0, n):\n",
    "            if left[i] == -1:\n",
    "                tleft = 0\n",
    "            else:\n",
    "                tleft = temp[left[i]]\n",
    "            \n",
    "            if right[i] == n:\n",
    "                tright = temp[-1]\n",
    "            else:\n",
    "                tright = temp[right[i]] - nums[right[i]] \n",
    "            tt = tright - tleft\n",
    "            res = max(res, nums[i] * tt)\n",
    "        \n",
    "        return res % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(nums)\n",
    "        pres = list(accumulate(nums, initial=0))\n",
    "        left = [-1] * n\n",
    "        right = [n] * n\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            while stack and nums[stack[-1]] >= nums[i]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                left[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "\n",
    "        stack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stack and nums[stack[-1]] >= nums[i]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                right[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans, (pres[right[i]] - pres[left[i] + 1]) * nums[i])\n",
    "\n",
    "        return ans % mod\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(nums)\n",
    "        pres = list(accumulate(nums, initial=0))\n",
    "        left = [-1] * n\n",
    "        right = [n] * n\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            while stack and nums[stack[-1]] >= nums[i]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                left[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "\n",
    "        stack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stack and nums[stack[-1]] >= nums[i]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                right[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans, (pres[right[i]] - pres[left[i] + 1]) * nums[i])\n",
    "\n",
    "        return ans % mod\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "kmod = 10**9 + 7\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        left = [-1] * n\n",
    "        s = []\n",
    "        for i in range(n):\n",
    "            while s and nums[s[-1]] >= nums[i]:\n",
    "                s.pop()\n",
    "            if s:\n",
    "                left[i] = s[-1]\n",
    "            s.append(i)\n",
    "\n",
    "\n",
    "        right = [n] * n\n",
    "        s = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while s and nums[s[-1]] >= nums[i]:\n",
    "                s.pop()\n",
    "            if s:\n",
    "                right[i] = s[-1]\n",
    "            s.append(i)\n",
    "\n",
    "        ans = 0\n",
    "        ps = list(accumulate(nums, initial=0))\n",
    "        for i in range(n):\n",
    "            l, r = left[i], right[i]\n",
    "            ans = max(ans, (ps[r] - ps[l + 1]) * nums[i])\n",
    "\n",
    "        return ans % kmod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        pre = [-1] * n\n",
    "        nxt = [n] * n\n",
    "\n",
    "        s = []\n",
    "        for i, x in enumerate(arr):\n",
    "            while s and x < arr[s[-1]]:\n",
    "                nxt[s.pop()] = i\n",
    "            s.append(i)\n",
    "\n",
    "        # 从右往左遍历\n",
    "        s = []\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while s and arr[i] <= arr[s[-1]]:\n",
    "                pre[s.pop()] = i\n",
    "            s.append(i)\n",
    "\n",
    "        ans = 0\n",
    "        pre_sum = list(accumulate(arr, initial = 0))\n",
    "        for i, x in enumerate(arr):\n",
    "            ans = max(ans, x * (pre_sum[nxt[i]] - pre_sum[pre[i]+1]))\n",
    "        return ans % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        acc = list(accumulate(nums, initial=0))\n",
    "        s = [0] * n\n",
    "        st = []\n",
    "        ans = 0\n",
    "        for idx, i in enumerate(nums):\n",
    "            while st and nums[st[-1]] > i:\n",
    "                tidx = st.pop()\n",
    "                if (t:= nums[tidx] * (acc[idx]-acc[s[tidx]])) > ans:\n",
    "                    ans = t\n",
    "            if st:\n",
    "                s[idx] = st[-1] + 1\n",
    "            st.append(idx)\n",
    "        for i in st:\n",
    "            ans = max(ans, nums[i] * (acc[-1]-acc[s[i]]))\n",
    "        return ans % (10 ** 9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        left=[-1]*n\n",
    "        st=[]\n",
    "        for i,val in enumerate(nums):\n",
    "            while st and val<=nums[st[-1]]:\n",
    "                st.pop()\n",
    "            if st:\n",
    "                left[i]=st[-1]\n",
    "            st.append(i)\n",
    "        right=[n]*n\n",
    "        st=[]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            val=nums[i]\n",
    "            while st and val<nums[st[-1]]:\n",
    "                st.pop()\n",
    "            if st:\n",
    "                right[i]=st[-1]\n",
    "            st.append(i)\n",
    "        preS=list(accumulate(nums,initial=0))\n",
    "        # print(left,right)\n",
    "        # print(preS)\n",
    "        res=0\n",
    "        mod=10**9+7\n",
    "        for i in range(n):\n",
    "            L,R=left[i]+1,right[i]-1\n",
    "            maxS=preS[R+1]-preS[L]\n",
    "            res=max(res,maxS*nums[i])\n",
    "        return res%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, arr: List[int]) -> int:\n",
    "        Mod = 10 ** 9 + 7\n",
    "        n = len(arr)\n",
    "        right = [n] * n\n",
    "        left = [-1] * n\n",
    "        stack1 = []\n",
    "        for i, x in enumerate(arr):\n",
    "            tmp = (x, i)\n",
    "            while stack1 and stack1[-1][0] > tmp[0]:\n",
    "                s = stack1.pop()\n",
    "                right[s[1]] = i\n",
    "            stack1.append(tmp)\n",
    "        stack1 = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            x = arr[i]\n",
    "            tmp = (x, i)\n",
    "            while stack1 and stack1[-1][0] > tmp[0]:\n",
    "                s = stack1.pop()\n",
    "                left[s[1]] = i\n",
    "            stack1.append(tmp)\n",
    "        ans = 0\n",
    "        Mod = 10 ** 9 + 7\n",
    "        # print(left)\n",
    "        # print(right)\n",
    "        acc = [0] * (n+1)\n",
    "        for i in range(n):\n",
    "            acc[i+1] = acc[i] + arr[i]\n",
    "        for i, x in enumerate(arr):\n",
    "            ans = max(ans, arr[i] * (acc[right[i]] - acc[left[i]+1]))\n",
    "        return ans % Mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        # 前缀和，+求每个数字左右小于它自己的index ,栈\n",
    "\n",
    "\n",
    "        # 递增栈\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        left = [0]*n\n",
    "        stack = [-1]\n",
    "        pre = [0]*(n+1)\n",
    "        for i,x in enumerate(nums):\n",
    "            pre[i+1] = pre[i]+nums[i]\n",
    "            while len(stack)>1 and x <= nums[stack[-1]]:\n",
    "                stack.pop()\n",
    "            left[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        ans = 0\n",
    "        right = [n]*n\n",
    "        stack = [n]\n",
    "        for j in range(n-1,-1,-1):\n",
    "            x = nums[j]\n",
    "            while len(stack)>1 and x <= nums[stack[-1]]:\n",
    "                stack.pop()\n",
    "            # print(stack)\n",
    "            right[j] = stack[-1]\n",
    "            stack.append(j)\n",
    "        print(left,right)\n",
    "        for i in range(n):\n",
    "            ans = max(ans, nums[i]*(pre[right[i]] - pre[left[i]+1]))\n",
    "\n",
    "        return ans %(10**9+7)\n",
    "        \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, s: List[int]) -> int:\n",
    "        f = list(accumulate(s, initial = 0))\n",
    "        n = len(s)\n",
    "        l, r = [0] * n, [n] * n\n",
    "        q = []\n",
    "        for i, v in enumerate(s):\n",
    "            while q and s[q[-1]] >= v:\n",
    "                r[q.pop()] = i\n",
    "            if q:\n",
    "                l[i] = q[-1] + 1\n",
    "            q.append(i)\n",
    "        res = max((f[r[i]] - f[l[i]]) * v for i, v in enumerate(s))\n",
    "        return res % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        pre_sum = [0]\n",
    "        for i in range(n):\n",
    "            pre_sum.append(pre_sum[-1] + nums[i])\n",
    "        \n",
    "        left_min = [-1] * n\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            while stack and nums[stack[-1]] >= nums[i]:\n",
    "                stack.pop()\n",
    "            \n",
    "            if stack:\n",
    "                left_min[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        \n",
    "        right_min = [n] *n\n",
    "        stack = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while stack and nums[stack[-1]] > nums[i]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                right_min[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        \n",
    "        \n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            left, right = left_min[i], right_min[i]\n",
    "            sum_ = pre_sum[right] - pre_sum[left + 1]\n",
    "            ans.append(nums[i] * sum_)\n",
    "        # print(left_min, right_min, ans)\n",
    "        return max(ans)%(10**9+7)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        # 前缀和，+求每个数字左右小于它自己的index ,栈\n",
    "\n",
    "\n",
    "        # 递增栈\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        left = [0]*n\n",
    "        stack = [-1]\n",
    "        pre = [0]*(n+1)\n",
    "        for i,x in enumerate(nums):\n",
    "            pre[i+1] = pre[i]+nums[i]\n",
    "            while len(stack)>1 and x <= nums[stack[-1]]:\n",
    "                stack.pop()\n",
    "            left[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        ans = 0\n",
    "        right = [n]*n\n",
    "        stack = [n]\n",
    "        for j in range(n-1,-1,-1):\n",
    "            x = nums[j]\n",
    "            while len(stack)>1 and x < nums[stack[-1]]:\n",
    "                stack.pop()\n",
    "            # print(stack)\n",
    "            right[j] = stack[-1]\n",
    "            stack.append(j)\n",
    "        print(left,right)\n",
    "        for i in range(n):\n",
    "            ans = max(ans, nums[i]*(pre[right[i]] - pre[left[i]+1]))\n",
    "\n",
    "        return ans %(10**9+7)\n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        nums = [0] + nums + [0]\n",
    "        pre_sum = [0]\n",
    "\n",
    "        for num in nums:\n",
    "            pre_sum.append(pre_sum[-1] + num)\n",
    "        \n",
    "        right_smaller = [0] * len(nums)\n",
    "        stack = []\n",
    "        for i in range(len(nums)):\n",
    "            while stack and nums[stack[-1]] > nums[i]:\n",
    "                cur = stack.pop()\n",
    "                right_smaller[cur] = i\n",
    "            stack.append(i)\n",
    "        left_smaller = [0] * len(nums)\n",
    "        stack = []\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            while stack and nums[stack[-1]] > nums[i]:\n",
    "                cur = stack.pop()\n",
    "                left_smaller[cur] = i\n",
    "            stack.append(i)\n",
    "\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            left, right = left_smaller[i], right_smaller[i]\n",
    "            res = max(res, nums[i] * (pre_sum[right] - pre_sum[left + 1]))\n",
    "        \n",
    "        return res % (10 ** 9 + 7)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # nums = [0] + nums + [0]\n",
    "        # presum = [0]\n",
    "        # for num in nums:\n",
    "        #     presum.append(presum[-1] + num)\n",
    "        \n",
    "        # res = 0\n",
    "\n",
    "        # right_min = [0] * len(nums)\n",
    "        # stack = []\n",
    "        # for i in range(len(nums)):\n",
    "        #     while stack and nums[stack[-1]] > nums[i]:\n",
    "        #         cur = stack.pop()\n",
    "        #         right_min[cur] = i\n",
    "        #     stack.append(i)\n",
    "        \n",
    "        # left_min = [0] * len(nums)\n",
    "        # stack = []\n",
    "        # for i in range(len(nums) - 1, -1, -1):\n",
    "        #     while stack and nums[stack[-1]] > nums[i]:\n",
    "        #         cur = stack.pop()\n",
    "        #         left_min[cur] = i\n",
    "        #     stack.append(i)\n",
    "\n",
    "\n",
    "        # for i in range(len(nums)):\n",
    "        #     num = nums[i]\n",
    "        #     left_num = left_min[i]\n",
    "        #     right_num = right_min[i]\n",
    "        #     res = max(res, num * (presum[right_num] - presum[left_num + 1]))\n",
    "        \n",
    "        # return res % (10 ** 9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        nums = [0] + nums + [0]\n",
    "        pre_sum = [0]\n",
    "        for num in nums:\n",
    "            pre_sum.append(pre_sum[-1] + num)\n",
    "        n = len(nums)\n",
    "        right_smaller = [0] * n\n",
    "        left_smaller = [0] * n\n",
    "\n",
    "        stack = []\n",
    "        for i in range(1, n):\n",
    "            while stack and nums[stack[-1]] > nums[i]:\n",
    "                cur = stack.pop()\n",
    "                right_smaller[cur] = i\n",
    "            stack.append(i)\n",
    "        \n",
    "        stack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stack and nums[stack[-1]] > nums[i]:\n",
    "                cur = stack.pop()\n",
    "                left_smaller[cur] = i\n",
    "            stack.append(i)\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            left, right = left_smaller[i], right_smaller[i]\n",
    "            res = max(res, (pre_sum[right] - pre_sum[left + 1]) * nums[i])\n",
    "        return res % (10 ** 9 + 7)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # nums = [0] + nums + [0]\n",
    "        # presum = [0]\n",
    "        # for num in nums:\n",
    "        #     presum.append(presum[-1] + num)\n",
    "        \n",
    "        # res = 0\n",
    "\n",
    "        # right_min = [0] * len(nums)\n",
    "        # stack = []\n",
    "        # for i in range(len(nums)):\n",
    "        #     while stack and nums[stack[-1]] > nums[i]:\n",
    "        #         cur = stack.pop()\n",
    "        #         right_min[cur] = i\n",
    "        #     stack.append(i)\n",
    "        \n",
    "        # left_min = [0] * len(nums)\n",
    "        # stack = []\n",
    "        # for i in range(len(nums) - 1, -1, -1):\n",
    "        #     while stack and nums[stack[-1]] > nums[i]:\n",
    "        #         cur = stack.pop()\n",
    "        #         left_min[cur] = i\n",
    "        #     stack.append(i)\n",
    "\n",
    "\n",
    "        # for i in range(len(nums)):\n",
    "        #     num = nums[i]\n",
    "        #     left_num = left_min[i]\n",
    "        #     right_num = right_min[i]\n",
    "        #     res = max(res, num * (presum[right_num] - presum[left_num + 1]))\n",
    "        \n",
    "        # return res % (10 ** 9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        nums = [0] + nums + [0]\n",
    "        n = len(nums)\n",
    "\n",
    "        presum = [0]\n",
    "        for num in nums:\n",
    "            presum.append(presum[-1] + num)\n",
    "\n",
    "        right_min = [-1] * n\n",
    "        stack = []\n",
    "        for i in range(1, n):\n",
    "            while stack and nums[stack[-1]] > nums[i]:\n",
    "                cur = stack.pop()\n",
    "                right_min[cur] = i\n",
    "            stack.append(i)\n",
    "        \n",
    "        left_min = [-1] * n\n",
    "        stack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stack and nums[stack[-1]] > nums[i]:\n",
    "                cur = stack.pop()\n",
    "                left_min[cur] = i\n",
    "            \n",
    "            stack.append(i)\n",
    "        res = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            left, right = left_min[i], right_min[i]\n",
    "            res = max(res, nums[i] * (presum[right] - presum[left + 1]))\n",
    "\n",
    "\n",
    "        return res % (10 ** 9 + 7)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # nums = [0] + nums + [0]\n",
    "        # presum = [0]\n",
    "        # for num in nums:\n",
    "        #     presum.append(presum[-1] + num)\n",
    "        \n",
    "        # res = 0\n",
    "\n",
    "        # right_min = [0] * len(nums)\n",
    "        # stack = []\n",
    "        # for i in range(len(nums)):\n",
    "        #     while stack and nums[stack[-1]] > nums[i]:\n",
    "        #         cur = stack.pop()\n",
    "        #         right_min[cur] = i\n",
    "        #     stack.append(i)\n",
    "        \n",
    "        # left_min = [0] * len(nums)\n",
    "        # stack = []\n",
    "        # for i in range(len(nums) - 1, -1, -1):\n",
    "        #     while stack and nums[stack[-1]] > nums[i]:\n",
    "        #         cur = stack.pop()\n",
    "        #         left_min[cur] = i\n",
    "        #     stack.append(i)\n",
    "\n",
    "\n",
    "        # for i in range(len(nums)):\n",
    "        #     num = nums[i]\n",
    "        #     left_num = left_min[i]\n",
    "        #     right_num = right_min[i]\n",
    "        #     res = max(res, num * (presum[right_num] - presum[left_num + 1]))\n",
    "        \n",
    "        # return res % (10 ** 9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(nums)\n",
    "        s = [0] * (n + 1)\n",
    "        for i, x in enumerate(nums):\n",
    "            s[i + 1] = s[i] + x\n",
    "            \n",
    "        pre = [0] * (n + 1)\n",
    "        suf = [0] * (n + 1)\n",
    "        stk = []\n",
    "        for i, x in enumerate(nums):\n",
    "            while stk and nums[stk[-1]] >= x:\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                pre[i + 1] = stk[-1] + 1\n",
    "            else:\n",
    "                pre[i + 1] = 0\n",
    "            stk.append(i)\n",
    "\n",
    "        stk = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stk and nums[stk[-1]] >= nums[i]:\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                suf[i + 1] = stk[-1]\n",
    "            else:\n",
    "                suf[i + 1] = n\n",
    "            stk.append(i)\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans, nums[i] * (s[suf[i + 1]] - s[pre[i + 1]]))\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        qz = [0]\n",
    "        for x in nums:\n",
    "            qz.append(x + qz[-1])\n",
    "        \n",
    "        l = len(nums)\n",
    "        rd = [l] * l\n",
    "        z = []\n",
    "        for i in range(l):\n",
    "            while z and nums[i] < nums[z[-1]]:\n",
    "                rd[z.pop()] = i\n",
    "            z.append(i)\n",
    "\n",
    "        ld = [0] * l\n",
    "        z = []\n",
    "        for i in range(l - 1, -1, -1):\n",
    "            while z and nums[i] < nums[z[-1]]:\n",
    "                ld[z.pop()] = i + 1\n",
    "            z.append(i)\n",
    "\n",
    "        return max(nums[i] * (qz[rd[i]] - qz[ld[i]]) for i in range(l)) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class MonoStack:\n",
    "    def __init__(self):\n",
    "        self.data = []\n",
    "    \n",
    "    def update(self, item):\n",
    "        if item >= self.data[-1]:\n",
    "            self.data.append(item)\n",
    "        else:\n",
    "            while self.data[-1] > item:\n",
    "                self.data.pop()\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        S = [0 for i in range(len(nums)+1)]\n",
    "        s = 0\n",
    "        for i in range(len(nums)):\n",
    "            s += nums[i]\n",
    "            S[i+1] = s\n",
    "        left = [0 for i in range(len(nums))]\n",
    "        right = [len(nums) for i in range(len(nums))]\n",
    "        monoStack = []\n",
    "        for i,n in enumerate(nums):\n",
    "            if len(monoStack) == 0 or (n, i) >= monoStack[-1]:\n",
    "                monoStack.append((n, i))\n",
    "            else:\n",
    "                while len(monoStack) > 0 and monoStack[-1] > (n, i):\n",
    "                    _, pos = monoStack.pop()\n",
    "                    right[pos] = i\n",
    "                monoStack.append((n, i))\n",
    "        monoStack = []\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            if len(monoStack) == 0 or (nums[i], i) >= monoStack[-1]:\n",
    "                monoStack.append((nums[i], i))\n",
    "            else:\n",
    "                while len(monoStack) > 0 and monoStack[-1] > (nums[i], i):\n",
    "                    _, pos = monoStack.pop()\n",
    "                    left[pos] = i + 1\n",
    "                monoStack.append((nums[i], i))\n",
    "        result = 0\n",
    "        for i in range(len(nums)):\n",
    "            val = (S[right[i]]-S[left[i]]) * nums[i]\n",
    "            if val > result:\n",
    "                result = val\n",
    "        return result%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        presum = [0]\n",
    "        for k in nums:\n",
    "            presum.append(k + presum[-1])\n",
    "\n",
    "        n = len(nums)\n",
    "        mod = 10 ** 9 + 7\n",
    "        left, right = [0] * n, [n-1] * n\n",
    "\n",
    "        s = []\n",
    "\n",
    "        for i,num in enumerate(nums):\n",
    "            while s and nums[s[-1]] >= num:\n",
    "                right[s[-1]] = i - 1\n",
    "                s.pop()\n",
    "            if s :\n",
    "                left[i] = s[-1] + 1\n",
    "            s.append(i)\n",
    "        \n",
    "        best = max((presum[right[i] + 1] - presum[left[i]]) * num for i, num in enumerate(nums))\n",
    "        return best % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        # 单调栈\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(nums)\n",
    "        left, right = [0] * n, [n - 1] * n \n",
    "        s = list() # 单调栈\n",
    "        for i, num in enumerate(nums):\n",
    "            while s and nums[s[-1]] >= num:\n",
    "                right[s[-1]] = i - 1\n",
    "                s.pop()\n",
    "            if s:\n",
    "                left[i] = s[-1] + 1\n",
    "            s.append(i)\n",
    "        \n",
    "        pre = [0]\n",
    "        for i, num in enumerate(nums):\n",
    "            pre.append(pre[-1] + num)\n",
    "        best = max((pre[right[i] + 1] - pre[left[i]]) * num for i, num in enumerate(nums))\n",
    "        return best % mod "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n = len(nums)\n",
    "        # 数组 left 初始化为 0，数组 right 初始化为 n-1\n",
    "        # 设置为元素不存在时的特殊值\n",
    "        left, right = [0] * n, [n - 1] * n\n",
    "        # 单调栈\n",
    "        s = list()\n",
    "        for i, num in enumerate(nums):\n",
    "            while s and nums[s[-1]] >= num:\n",
    "                # 这里的 right 是非严格定义的，right[i] 是右侧最近的小于等于 nums[i] 的元素下标\n",
    "                right[s[-1]] = i - 1\n",
    "                s.pop()\n",
    "            if s:\n",
    "                # 这里的 left 是严格定义的，left[i] 是左侧最近的严格小于 nums[i] 的元素下标\n",
    "                left[i] = s[-1] + 1\n",
    "            s.append(i)\n",
    "        # 前缀和\n",
    "        pre = [0]\n",
    "        for i, num in enumerate(nums):\n",
    "            pre.append(pre[-1] + num)\n",
    "        best = max((pre[right[i] + 1] - pre[left[i]]) * num for i, num in enumerate(nums))\n",
    "        return best % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "\n",
    "        n = len(nums)\n",
    "        # 数组 left 初始化为 0，数组 right 初始化为 n-1\n",
    "        # 设置为元素不存在时的特殊值\n",
    "        left, right = [0] * n, [n - 1] * n\n",
    "        # 单调栈\n",
    "        s = list()\n",
    "        for i, num in enumerate(nums):\n",
    "            while s and nums[s[-1]] >= num:\n",
    "                # 这里的 right 是非严格定义的，right[i] 是右侧最近的小于等于 nums[i] 的元素下标\n",
    "                right[s[-1]] = i - 1\n",
    "                s.pop()\n",
    "            if s:\n",
    "                # 这里的 left 是严格定义的，left[i] 是左侧最近的严格小于 nums[i] 的元素下标\n",
    "                left[i] = s[-1] + 1\n",
    "            s.append(i)\n",
    "        \n",
    "        # 前缀和\n",
    "        pre = [0]\n",
    "        for i, num in enumerate(nums):\n",
    "            pre.append(pre[-1] + num)\n",
    "        \n",
    "        best = max((pre[right[i] + 1] - pre[left[i]]) * num for i, num in enumerate(nums))\n",
    "        return best % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        mod = 10**9+7\n",
    "        s = []\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        right = [n-1]*n\n",
    "        left = [0]*n\n",
    "        for i,v in enumerate(nums):\n",
    "            while s and nums[s[-1]]>=v:\n",
    "                right[s[-1]] = i-1\n",
    "                s.pop()\n",
    "            if s:\n",
    "                left[i] = s[-1]+1\n",
    "            s.append(i)\n",
    "        pre = [0]\n",
    "        for i,v in enumerate(nums):\n",
    "            pre.append(pre[-1]+v) \n",
    "        for i,v in enumerate(nums):\n",
    "            ans = max(ans,((pre[right[i]+1]-pre[left[i]])*v))\n",
    "        return ans%mod\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        left_min = [n] * n\n",
    "        right_min = [0] * n\n",
    "        stack = []\n",
    "        preSum = [0]\n",
    "        for i,num in enumerate(nums):\n",
    "            preSum.append(preSum[-1]+num)\n",
    "            while stack and stack[-1][1] > num:\n",
    "                index,_ = stack.pop()\n",
    "                left_min[index] = i\n",
    "            if stack:\n",
    "                right_min[i] = stack[-1][0] + 1\n",
    "            stack.append((i,num))\n",
    "        # print(left_min)\n",
    "        # print(right_min)\n",
    "        return max(nums[i] * (preSum[left_min[i]]-preSum[right_min[i]]) for i in range(n)) % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        nums = [0] + nums + [0]\n",
    "        n = len(nums)\n",
    "        pre_sum = [0]\n",
    "        for num in nums:\n",
    "            pre_sum.append(pre_sum[-1] + num)\n",
    "        \n",
    "        right_smaller = [0] * n\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            while stack and nums[stack[-1]] > nums[i]:\n",
    "                cur = stack.pop()\n",
    "                right_smaller[cur] = i\n",
    "            \n",
    "            stack.append(i)\n",
    "        \n",
    "        left_smaller = [0] * n\n",
    "        stack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stack and nums[stack[-1]] > nums[i]:\n",
    "                cur = stack.pop()\n",
    "                left_smaller[cur] = i\n",
    "\n",
    "            stack.append(i)\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            left, right = left_smaller[i], right_smaller[i]\n",
    "            res = max(res, nums[i] * (pre_sum[right] - pre_sum[left + 1]))\n",
    "        \n",
    "        return (res) % (10**9+7)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # nums = [0] + nums + [0]\n",
    "        # presum = [0]\n",
    "        # for num in nums:\n",
    "        #     presum.append(presum[-1] + num)\n",
    "        \n",
    "        # res = 0\n",
    "\n",
    "        # right_min = [0] * len(nums)\n",
    "        # stack = []\n",
    "        # for i in range(len(nums)):\n",
    "        #     while stack and nums[stack[-1]] > nums[i]:\n",
    "        #         cur = stack.pop()\n",
    "        #         right_min[cur] = i\n",
    "        #     stack.append(i)\n",
    "        \n",
    "        # left_min = [0] * len(nums)\n",
    "        # stack = []\n",
    "        # for i in range(len(nums) - 1, -1, -1):\n",
    "        #     while stack and nums[stack[-1]] > nums[i]:\n",
    "        #         cur = stack.pop()\n",
    "        #         left_min[cur] = i\n",
    "        #     stack.append(i)\n",
    "\n",
    "\n",
    "        # for i in range(len(nums)):\n",
    "        #     num = nums[i]\n",
    "        #     left_num = left_min[i]\n",
    "        #     right_num = right_min[i]\n",
    "        #     res = max(res, num * (presum[right_num] - presum[left_num + 1]))\n",
    "        \n",
    "        # return res % (10 ** 9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rightSmaller(self, nums):\n",
    "        n = len(nums)\n",
    "        res = [0] * n\n",
    "        s = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while s and nums[s[-1]] >=nums[i]:\n",
    "                s.pop()\n",
    "            res[i] = n-1 if not s else s[-1] - 1\n",
    "            s.append(i)\n",
    "        return res\n",
    "    def leftSmaller(self,nums):\n",
    "        n = len(nums)\n",
    "        res = [0] * n\n",
    "        s = []\n",
    "        for i in range(n):\n",
    "            while s and nums[s[-1]] >= nums[i]:\n",
    "                s.pop()\n",
    "            res[i] = 0 if not s else s[-1] + 1\n",
    "            s.append(i)\n",
    "        return res\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        left = self.leftSmaller(nums)\n",
    "        right = self.rightSmaller(nums)\n",
    "        preSum = [0] * (len(nums) + 1)\n",
    "        for i in range(len(nums)):\n",
    "            preSum[i+1] = nums[i] + preSum[i]\n",
    "        maxRes = 1\n",
    "        for i in range(len(nums)):\n",
    "            maxRes = max(maxRes, (preSum[right[i]+1] - preSum[left[i]])*nums[i])\n",
    "        return maxRes % (10 ** 9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rightSmaller(self, nums):\n",
    "        n = len(nums)\n",
    "        right = [n-1] * n\n",
    "        s = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while s and nums[s[-1]] >= nums[i]:\n",
    "                s.pop()\n",
    "            right[i] = s[-1] - 1 if s else n - 1\n",
    "            s.append(i)\n",
    "        return right\n",
    "\n",
    "    def leftSmaller(self, nums):\n",
    "        n = len(nums)\n",
    "        left = [0] * n\n",
    "        s = []\n",
    "        for i in range(n):\n",
    "            while s and nums[s[-1]] >= nums[i]:\n",
    "                s.pop()\n",
    "            left[i] = s[-1] + 1 if s else 0\n",
    "            s.append(i)\n",
    "        return left\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        left = self.leftSmaller(nums)\n",
    "        right = self.rightSmaller(nums)\n",
    "        res = float(\"-inf\")\n",
    "        preSum = [0] * (n+1)\n",
    "        for i in range(n):\n",
    "            preSum[i+1] = preSum[i] + nums[i]\n",
    "        for i in range(n):\n",
    "            res = max(res, (preSum[right[i]+1] - preSum[left[i]]) * nums[i])\n",
    "        return res % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        prefix = [0] * (n + 1)\n",
    "        for i, x in enumerate(nums):\n",
    "            prefix[i + 1] = prefix[i] + x\n",
    "        left = [0] * n\n",
    "        right = [n - 1] * n\n",
    "        st = []\n",
    "        for i in range(n):\n",
    "            while st and nums[i] < nums[st[-1]]:\n",
    "                right[st.pop()] = i - 1\n",
    "            st.append(i)\n",
    "        st = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while st and nums[i] < nums[st[-1]]:\n",
    "                left[st.pop()] = i + 1\n",
    "            st.append(i)\n",
    "        # print(left, right)\n",
    "        ans = 0\n",
    "        MOD = 10 ** 9 + 7\n",
    "        for i in range(n):\n",
    "            ans = max(ans, nums[i] * (prefix[right[i] + 1] - prefix[left[i]]))\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumMinProduct(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        prefix=[i for i in accumulate(nums,initial=0)]\n",
    "        stack=[]\n",
    "        l,r=[0]*n,[n]*n\n",
    "        ans=0\n",
    "        for i,x in enumerate(nums):\n",
    "            while stack and nums[stack[-1]]>x:\n",
    "                p=stack.pop()\n",
    "                r[p]=i\n",
    "            stack.append(i)\n",
    "        stack=[]\n",
    "        for i,x in enumerate(nums[::-1]):\n",
    "            while stack and nums[stack[-1]]>x:\n",
    "                p=stack.pop()\n",
    "                l[p]=n-i\n",
    "            stack.append(n-1-i)\n",
    "        #print(l,r)\n",
    "        return max((prefix[r[i]]-prefix[l[i]])*nums[i] for i in range(n))%(10**9+7)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
